\documentclass{article}
\usepackage{mathtools} 
\usepackage{fontspec}
\usepackage[UTF8]{ctex}
\usepackage{amsthm}
\usepackage{mdframed}
\usepackage{xcolor}
\usepackage{amssymb}
\usepackage{amsmath}


% 定义新的带灰色背景的说明环境 zremark
\newmdtheoremenv[
  backgroundcolor=gray!10,
  % 边框与背景一致，边框线会消失
  linecolor=gray!10
]{zremark}{说明}


\begin{document}
\title{8.5 习题}
\author{张志聪}
\maketitle

这一节题太多了，我只写正文中提到的习题了。

\section*{8.5.3}

证明是偏序集。
\begin{itemize}
  \item （自反性）因为对任意的正整数$x$都有$x = x \times 1$，所以$x | x$
  \item （反对称性）如果正整数$x, y$满足$x | y$且$y | x$，那么存在正整数$a,b$使得
        \begin{equation*}
          \begin{cases*}
            y = x \times a \\
            x = y \times b
          \end{cases*}
        \end{equation*}
        $\Rightarrow$
        \begin{equation*}
          \begin{cases*}
            a = 1 \\
            b = 1
          \end{cases*}
        \end{equation*}
        于是$x = y$
  \item （传递性）如果正整数$x, y, z$满足$x | y$且$y | z$，那么存在正整数$a,b$使得
        \begin{equation*}
          \begin{cases*}
            y = x \times a \\
            z = y \times b
          \end{cases*}
        \end{equation*}
        $\Rightarrow$
        \begin{equation*}
          \begin{cases*}
            z = x \times a \times b
          \end{cases*}
        \end{equation*}
        于是$x | z$
\end{itemize}

证明不是全序集，举一个反例即可，正整数$2,3$是不满足$2 | 3$或$3 | 2$的，因为不存在正整数$a$使得
$2 = 3a$或$3 = 2a$。

\section*{8.5.7}

设$\leq_{X}$是$X$上的序关系。

反证法，假设$Y$有多个最小元素。
假设$y_1, y_2 \in Y$且$y_1 \neq y_2$都是$Y$的最小元素。
由于$Y$是$X$的一个全序子集，则由定义8.5.3可知，$y_1 \leq_{X} y_2$或$y_2 \leq_{X} y_1$。

如果$y_1 \leq_{X} y_2$则与$y_2$是最小值相悖；
如果$y_2 \leq_{X} y_1$则与$y_1$是最小值相悖。

最大值的证明同上。

\section*{8.5.8}
为了描述方便，不妨设$X$是全序集，$Y$是$X$的一个非空子集，$\leq_X$是$X$上的序关系。

按照定义8.5.3可知，全序集的非空子集也是全序集。

由题设可知$Y$是有限集合，所以不妨设$\#(Y) = n$，$n$是任意自然数。

对$n$进行归纳。

归纳基始，$n = 1$，即$Y$中只有一个元素，由定义8.5.5可知，该元素既是最大值也是最小值。

归纳假设，$n = k$时命题成立。

$n = k + 1$，设$Y^\prime = Y \setminus \{x\}$，$x$可以是$Y$中的任意元素。
由引理3.6.9可知，$\#(Y^\prime) = k$，于是利用归纳假设可得$min(Y^\prime) = y_1$，
因为$Y$是全序集，所以$x, y_1$是可以比较大小的，
即：要么$x \leq_X y_1$（此时$x$是最小值），要么$y_1 \leq_X x$（此时$y_1$是最小值）。

最大值证明类似。

\section*{8.5.10}

\begin{zremark}
  “强归纳原理和弱归纳原理是等价的”。个人感觉这个命题还是挺重要的，接下来我会证明这个命题。

  这里的证明，参考了《符号逻辑讲义$_\text{徐明}$》命题681.
  \begin{itemize}
    \item 强归纳原理 $\Rightarrow$ 弱归纳原理；
          即强归纳原理成立的前提下，可以推出弱归纳原理成立。

          令$P(n)$是关于元素$n \in X$的任意性质。假设弱归纳原理的前提成立，即假设$P(0)$成立，
          并归纳假设对每一个$n \in X, P(n)$成立则$P(n+1)$成立。
          现在需要用强归纳原理证明弱归纳原理的结论（对所有的$n$都有$P(n)$）。而强归纳原理的前提
          对所有$m \leq n$的$P(m)$成立，那么$P(n+1)$成立，这显然已由弱归纳原理的前提保证了。
          强归纳原理的前提满足后，结论也就有了。


    \item 弱归纳原理 $\Rightarrow$ 强归纳原理

          即弱归纳原理成立的前提下，可以推出强归纳原理成立。

          令$P(n)$是关于元素$n \in X$的任意性质。假设强归纳原理的前提成立，
          即对所有$m \leq n$的$P(m)$成立，那么$P(n+1)$成立。
          现在需要用弱归纳原理证明强归纳原理的结论。而弱归纳原理的前提$P(0)$成立，
          与对每一个$n \in X, P(n)$成立则$P(n+1)$成立，这显然也已被强归纳原理的前提保证了，
          弱归纳原理的前提满足后，结论也就有了。
  \end{itemize}
  上面的证明是在自然数集上证明的，但该命题在良序集也是成立的。

  下面说一下大致原因，不是很严谨：

  \begin{enumerate}
    \item 你可能会说书中是$m < n$的$m \in X$都为真，那么$P(n)$也为真。
          而不是以上证明中的$m \leq n$，
          两种方式是等价的：都是表达定义8.5.12中的最小严格上界。
    \item 也有可能对$n + 1$表示困惑，因为良序集里不一定有加法定义，
          其实$n + 1$是自然数中表达$m \leq n$严格最小上界的方式。
  \end{enumerate}

\end{zremark}

反证法，假设结论不成立。

% 即存在$n \in X$使得$P(n)$为假。而这明显与强归纳原理的前提矛盾，当然直接这么说不够严谨，下面按照提示，进行详细说明；

即$Y := \{n \in X: P(m) \text{为假},  m \leq n, m \in X  \}$
（这里我改了下表达方式，感觉书中的翻译有点不直观）不是空集。

因为$Y$是$X$的非空子集，那么也是良序集，所以存在最小值$M$

\begin{itemize}
  \item 如果$M = 0$，这里假设$0$是$X$的最小值，因为$X$是良序集，最小值是肯定存在的。这与前提条件矛盾，因为按照前提条件$P(0)$是空虚为真的。
  \item 如果$M > 0$，那么，存在$0 \leq m < M, P(m)$为真，由前提条件可知$P(M)$为真，存在矛盾。
\end{itemize}

\section*{8.5.11}
\begin{itemize}
  \item $\Rightarrow$ 由定义8.5.8可知，$Y \cup Y^\prime$是全序的
  \item $\Leftarrow$ 
        设$A$是$Y \cup Y^\prime$的任意一个非空子集，
        因为$A$中元素要么属于$Y$，要么属于$Y^\prime$，
        所以可以设
        \begin{align*}
          A = A_Y \cup A_Y^\prime
        \end{align*}
        其中$A_Y \subseteq Y, A_Y^\prime \subseteq Y^\prime$。

        因为$A$是非空子集，所以$A_Y, A_Y^\prime$至少有一个是非空的，
        因为$Y, Y^\prime$都是良序集，所以$A_Y, A_Y^\prime$非空的情况下都是良序集，
        即有最小值$m, m^\prime$；
        如果两个都不为空，因为$Y \cup Y^\prime$是全序集，所以$A$也是全序集，
        于是$m, m^\prime$可以通过比较大小
        得出最小值。
        
        既然$A$的最小值可以找到，那么，由$A$的任意性，可得$Y \cap Y^\prime $是良序集。


\end{itemize}

\section*{8.5.13}

\begin{zremark}
  这个结论不是太直观，书中定义“好的”，其实是想保证子集$Y$都是按照相同顺序放入元素的。

  举个直观的例子，比如$x_0 = 0$，那么，定义不满足条件的子集$Y,Y^\prime$如下：
  \begin{align*}
    Y        & := \{0, 1, 2, 3, 4,...\} \\
    Y^\prime & := \{ 0, 1, 2, 4,... \}
  \end{align*}

  前者$\{y \in Y: y < 3\} = \{0, 1, 2\}, s(\{y \in Y: y < 3\}) = 3$；
  后者是$\{y \in Y^\prime: y < 4\} = \{0, 1, 2\}, s(\{y \in Y^\prime: y < 4\}) = 4$。

  这与函数的定义矛盾，相同的自变量$\{0, 1, 2\}$对应函数值$s(\{0, 1, 2\})$却不一样。
\end{zremark}

按照提示进行证明。

\textbf{（1）先利用命题8.5.10（强归纳原理）证明
  \begin{align*}
    \{y \in Y: y \leq a \} = \{y \in Y^\prime: y \leq a \} = \{y \in Y \cap Y^\prime: y \leq a \}
  \end{align*}
  对所有的$a \in Y \cap Y^\prime$均成立。}

$Y \cap Y^\prime \neq \varnothing$，因为两个集合中至少有一个元素$x_0$，设$a \in Y \cap Y^\prime$，
接下来对$a$进行强归纳。

对每一个$n \in Y \cap Y^\prime$，对所有满足$m < n, m \in Y \cap Y^\prime$的$m$命题均成立，
现在需要证明$a=n$等式也成立。

\textit{（说明：证明思路和说明中一致，只是更加严谨）}

反证法，假设$a=n$时不成立，即在$m, n$之间存在元素$y_0 \not \in Y \cap Y^\prime$， 那么，集合
\begin{align*}
  W := \{ y: m < y <n, y \not \in Y \cap Y^\prime, y \in Y \text{or } y \in Y^\prime \}
\end{align*}
是非空集合。

因为$Y,Y^\prime$都是良序集，所以$W$也是良序集，所以存在最小元素$w \in W$，
不妨设$w \in Y$，另外取$w^\prime$是$W$中$Y^\prime$的最小值（没有，则取$n$）（可以取到最小值的原因是$W \setminus Y$也是良序集），
此时$s(\{ y \in Y: y < w \}) = w$, $s(\{ y \in Y^\prime: y < w^\prime \}) = w^\prime$，
但由归纳假设可知，$\{y \in Y: y \leq m \} = \{y \in Y^\prime: y \leq m \}$，那么，
\begin{align*}
  \{ y \in Y: y < w \} = \{ y \in Y^\prime: y < w^\prime \}
\end{align*}
但函数$s$对应的函数值却不一致，这与函数定义矛盾。


\textbf{（2）接下来，证明$Y \cap Y^\prime$是好的。}

反证法，假设$Y \cap Y^\prime$不是好的，即存在$k \in Y \cap Y^\prime$，
使得$s({y \in Y \cap Y^\prime : y < k }) \neq k$。

由（1）可知$\{y \in Y : y \leq k \} = \{y \in Y \cap Y^\prime : y \leq k \}$，
\begin{equation*}
  \begin{cases*}
    \{y \in Y : y \leq k \} \setminus \{k\}                = \{y \in Y : y < k \} \\
    \{y \in Y \cap Y^\prime : y \leq k \} \setminus \{k\}  = \{y \in Y \cap Y^\prime : y < k \}
  \end{cases*}
\end{equation*}
可知
\begin{align*}
  \{y \in Y : y < k \} = \{y \in Y \cap Y^\prime : y < k \}
\end{align*}
于是，$s(\{y \in Y : y < k \}) \neq k$与$Y$是“好的”矛盾

\textbf{（3）如果$Y^\prime \setminus Y$是非空的，$s(Y \cap Y^\prime) = min(Y^\prime \setminus Y )$
  并且$Y^\prime \setminus Y$的每个元素都是$Y$的严格上界。}

不妨设$y_{min}=min(Y^\prime \setminus Y)$，由严格上界的定义可知，我们需要证明，对任意$y \in Y$都有$y_{min} > y$。
下面对$y$进行强归纳。

假设对所有$y_m < y_n$的$y_m \in Y$时命题都为真，下面需证明$y_n$时命题也为真。

\begin{itemize}
  \item 归纳基始$y_n = x_0$，由$Y,Y^\prime$都是以$x_0$为最小元素的良序集可知$y_{min} > x_0$。
  \item  反证法，$y_n \geq y_{min}$，因为$y_{min} \not \in Y$所以$y_n \neq y_{min}$，于是$y_n > y_{min}$。

        先证明下，$y_{min}$之前$Y, Y^\prime$的元素相同。
        反证法，如果不相同，会导致$Y \cap Y^\prime$出现空洞，而由（2）可知，$Y \cap Y^\prime$也是好的，
        进而会出现与“说明”中一样的问题，这里就不在赘述了。

        于是
        \begin{align*}
          \{ y : y \in Y, y < y_{min}\} & = \{ y : y \in Y^\prime, y < y_{min} \} \\
        \end{align*}
        又因为$y_{min} \not \in Y$且$y_n > y_{min}$和归纳假设对所有$y_m < y_n$都有$y_{min} > y_m $
        所以，
        \begin{align*}
          \{ y : y \in Y, y < y_{min}\} = \{ y : y \in Y, y < y_{n}\} & = \{ y : y \in Y^\prime, y < y_{min} \} \\
        \end{align*}

        因为$y_{min} \in Y^\prime, y_n \in Y$且是好的，所以
        \begin{align*}
          s(\{ y : y \in Y, y < y_n\})            & = y_n     \\
          s(\{ y : y \in Y^\prime, y < y_{min}\}) & = y_{min} \\
        \end{align*}
        因为
        \begin{align*}
          \{ y : y \in Y, y < y_{n}\} & = \{ y : y \in Y^\prime, y < y_{min} \} \\
        \end{align*}
        于是
        \begin{align*}
          y_n = y_{min}
        \end{align*}
        于是与$y_n > y_{min}$存在矛盾。
\end{itemize}

\section*{8.5.14}

反证法，假设$X$没有最大元素。那么$A$是$X$任意一个有上界的子集，不妨设其上界是$M$，
因为$X$没有最大元素，所以存在元素$x \in X$，使得$x > M$，由定义8.5.12可知，
$x$就是$A$的严格上界。

由引理8.5.14可知，可以构造一个以某个元素$x_0 \in X$为最小元素，没有严格上界的良序子集$Y$。
因为良序集$Y$也是全序集，按照题设$Y$有上界，由之前的结论可知有严格上界，
于是，存在矛盾，假设不成立。



\end{document}
